Cryptographic algorithms are widely used for encryption of messages, authentication, encryption signatures and identification. The well-known DES (Data Encryption Standard) has been in use for a long time, and was updated by Triple-DES, which has been replaced in many applications by AES (Advanced Encryption Standard). AES is an approved encryption standard by the U.S. government. AES is a substitution permutation network, that is fast enough to execute in both computer software and hardware implementations, relatively easy to implement, and requires little memory space.
Implementations of AES do not provide much security against an attacker recovering a secret key, if the attacker has privileged access to the system implementing the cipher. However, AES is often used in potentially insecure environments. For instance, AES could be employed in a white box environment. In a white box model, it is presumed that an attacker has total access to the system performing an encryption, including being able to observe directly a state of memory, program execution, and so on. In such a model, an encryption key can be observed in or extracted from memory, ways to conceal operations indicative of a secret key are therefore important. For example, the attacker can learn the secret key of an AES software implementation by observing the execution of the key scheduling algorithm.
Digital rights management (DRM) applications are one instance where it is desired to keep the attacker from finding the secret key even though the attacker has complete control of the execution process. “White-Box Cryptography and an AES Implementation”, by Stanley Chow, Philip A. Eisen, Harold Johnson, Paul C. van Oorschot, in Selected Areas in Cryptography: 9th Annual International Workshop, SAC 2002, PP. 250-270, gives a construction of the AES algorithm for such white box model. The security of this construction resides in the use of table lookups and masked data. The input and output mask applied to this data is never removed along the process. In this solution, there is a need for knowing the key value at the compilation time, or at least to be able to derive the tables from the original key in a secure environment.
However, this solution does not solve all needs for block cipher's encryption. Indeed, the case where the key is derived through a given process and then unknown at the compilation time is not included. One typical use case is when a program is distributed over several users and each of them has their own key. In this case, it is from a practical point of view impossible to disseminate different code to each user. Another use case is when generating session keys (which are different for each session) through a given process. Of course, in this case the key is unknown at compilation time. Another use case is when it is necessary to store a large number of keys. However, it is not reasonable to consider storing around 700 KB for each key.